A computer network enables various devices, such as processors, mass storage devices, and printers to communicate with each other over high speed bi-directional communication links. The devices are connected, that is, interfaced, to the network, and thus transfer data to and from the network, through nodes. The nodes are interconnected by the communication links. Networks may be of any size. For example, a network may contain several hundred or several thousand nodes, enabling devices at many different locations to communicate.
The nodes at either end of a communication link are commonly referred to as neighboring nodes. To send information to non-neighboring nodes, a node transmits the information over one or more network communication links to one or more neighboring nodes, and the neighboring nodes transmit the information to their neighboring node(s), etc.
Data and control messages are transmitted over the network in the form of packets. The packets contain, in addition to the data or control messages, network specific information, such as the identity of the first node transmitting the packet on to the network, i.e., the originating node. This information is in a first section of the packet referred to as a header. The header section immediately precedes the data or control message.
This invention involves broadcasting packets over a network. Broadcasting consists of sending a packet to every node on the network. This is easily accomplished over certain networks, such as networks configured in relatively simple topologies, i.e., rings. However, it is not as easily performed over networks which are configured with multiple paths between nodes.
One well known method of broadcasting packets over the network is flooding. Flooding requires a node receiving a packet to transmit it to each of its neighboring nodes, except the node from which it was received. The node thus copies the packet and transmits the copies over the appropriate communication links to the neighboring nodes. Copies of the packet eventually travel throughout the network to every node over every communication link. Typically multiple copies of the packet travel to every node. Thus the nodes must process each of the copies.
A packet traveling over a network may be lost or corrupted due to improperly operating nodes, that is, nodes with hardware faults or software glitches or bugs, and/or network misconfigurations. Thus it is desirable to design a robust transmittal scheme to deliver packets over a network containing improperly operating nodes. This scheme should also deliver packets over a network which is misconfigured.
Improperly operating nodes may delay packets, sporadically lose packets, alter packets, fail to transmit packets to or from a particular node and thus disrupt the broadcasting of one or more specific packets. An improperly operating node may also generate such a high volume of traffic, for example, by transmitting packets at a rate which is faster than the network nodes can process, so as to congest the entire network. Thus a mechanism is desirable to transmit packets successfully over a network containing improperly operating nodes. This mechanism should also effectively control the transmission of duplicated packets.
Nodes may operate "maliciously" as a result of, for example, network sabotage. A malicious node may delay, alter and/or fail to broadcast particular packets or it may purposefully broadcast inaccurate or conflicting information in a form which appears correct. The recipient of this apparently correct information can not determine whether it is reliable or unreliable. Thus a mechanism is desirable to select and broadcast only reliable information over a network containing malicious nodes.